গ্রিডি মেথড এবং এর কার্যকারিতা

গ্রিডি মেথড (Greedy Method) একটি সমস্যা সমাধানের কৌশল যা সিদ্ধান্ত নেওয়ার সময় সর্বদা সর্বাধিক স্থানীয়ভাবে সর্বোত্তম বিকল্প (locally optimal choice) বেছে নেয়। এটি সাধারণত এমন সমস্যা সমাধানে ব্যবহৃত হয় যেখানে প্রতিটি পদক্ষেপের সঠিকতা পরবর্তী পদক্ষেপের জন্য সহায়ক। গ্রিডি অ্যালগরিদমগুলি সাধারণত সহজ এবং দ্রুত, কিন্তু সবসময় গ্লোবাল অপটিমাম সমাধান প্রদান করে না।

গ্রিডি মেথডের মৌলিক বৈশিষ্ট্য

স্থানীয় সিদ্ধান্ত: গ্রিডি মেথডের মূল ধারণা হল স্থানীয়ভাবে সর্বোত্তম সিদ্ধান্ত নেওয়া, যা পরবর্তী সিদ্ধান্তগুলিতে ইতিবাচক প্রভাব ফেলবে।

পুনরাবৃত্তিমূলক ব্যবহার: গ্রিডি মেথড সমস্যাকে ছোট ছোট অংশে বিভক্ত করে এবং প্রতিটি অংশের জন্য স্থানীয়ভাবে সর্বোত্তম সিদ্ধান্ত গ্রহণ করে।

গ্লোবাল অপটিমাম: কিছু সমস্যায়, স্থানীয়ভাবে সর্বোত্তম সিদ্ধান্তগুলি গ্লোবাল অপটিমাম তৈরি করে, কিন্তু সবসময় তা হয় না।

গ্রিডি মেথডের কার্যকারিতা

গ্রিডি অ্যালগরিদমগুলি বিভিন্ন সমস্যা সমাধানে ব্যবহার করা হয়। নিচে কয়েকটি সাধারণ সমস্যা এবং তাদের গ্রিডি অ্যালগরিদম নিয়ে আলোচনা করা হলো:

কেনা-ব্যবসা সমস্যা (Activity Selection Problem):

• বিবরণ: একটি সেট অ্যাক্টিভিটিতে সর্বাধিক সংখ্যক নন-ওভারল্যাপিং অ্যাক্টিভিটি নির্বাচন করা।
• অ্যালগরিদম:
  1. অ্যাক্টিভিটিগুলি তাদের শেষ সময় অনুযায়ী সাজান।
  2. প্রথম অ্যাক্টিভিটি নির্বাচন করুন।
  3. পরবর্তী অ্যাক্টিভিটি নির্বাচন করুন যা নির্বাচিত অ্যাক্টিভিটির শেষে শুরু হয়।

কেনা-ব্যবসা সমস্যা (Fractional Knapsack Problem):

• বিবরণ: সর্বাধিক মান অর্জন করার জন্য একটি নির্দিষ্ট ধারণ ক্ষমতার মধ্যে বিভিন্ন ওজনের এবং মানের বস্তু নির্বাচন করা।
• অ্যালগরিদম:
  1. বস্তুগুলিকে তাদের মূল্য/ওজন অনুপাত অনুযায়ী সাজান।
  2. যতক্ষণ না ব্যাগ পূর্ণ হয়, সর্বাধিক মূল্যবান বস্তু যুক্ত করুন এবং প্রয়োজন অনুযায়ী বস্তু ভেঙে (fractional) যোগ করুন।

মিনিমাম স্প্যানিং ট্রি (Minimum Spanning Tree):

• বিবরণ: একটি গ্রাফের সমস্ত নোডের জন্য সর্বনিম্ন মোট ওজনের স্প্যানিং ট্রি তৈরি করা।
• অ্যালগরিদম: ক্রুস্কাল (Kruskal’s) বা প্রিম (Prim’s) অ্যালগরিদম ব্যবহার করা।

উদাহরণ (কেনা-ব্যবসা সমস্যা)

def fractional_knapsack(weights, values, capacity):
    index = list(range(len(values)))
    ratio = [v / w for v, w in zip(values, weights)]
    index.sort(key=lambda i: ratio[i], reverse=True)

    max_value = 0
    for i in index:
        if weights[i] <= capacity:
            max_value += values[i]
            capacity -= weights[i]
        else:
            max_value += values[i] * (capacity / weights[i])
            break
    return max_value

# ব্যবহার
weights = [10, 20, 30]
values = [60, 100, 120]
capacity = 50
print(f"Maximum value in Knapsack = {fractional_knapsack(weights, values, capacity)}")  # আউটপুট: 240.0

উপসংহার

গ্রিডি মেথড একটি সহজ এবং কার্যকরী সমস্যা সমাধানের কৌশল। যদিও এটি সবসময় গ্লোবাল অপটিমাম সমাধান প্রদান করে না, তবে এটি অনেক বাস্তব জীবনের সমস্যায় কার্যকরী হয়। গ্রিডি অ্যালগরিদমগুলি দ্রুত সমাধান প্রদান করে এবং জটিলতা কমাতে সহায়ক। কিছু নির্দিষ্ট সমস্যা সমাধানের জন্য গ্রিডি পদ্ধতির ব্যবহার একটি শক্তিশালী কৌশল হয়ে দাঁড়ায়।